package com.zhugang.week07;

/**
 * @program algorithms
 * @description: treeToDoublyList
 * @author: chanzhugang
 * @create: 2022/07/27 16:10
 */
public class TreeToDoublyList {


    /**
     * 剑指offer 36 二叉搜索树与双向链表
     *
     * @param root
     * @return
     */
    private Node dummyHead = new Node();
    private Node tail = dummyHead;

    public Node treeToDoublyList(Node root) {
        // 左指针指向前驱、右指针指向后继， 有序（中序遍历）
        // 画图理解
        if (root == null) {
            return null;
        }
        dfs(root);
        // 处理首尾相连（循环链表）
        tail.right = dummyHead.right;
        dummyHead.right.left = tail;
        return dummyHead.right;
    }

    private void dfs(Node root) {
        if (root == null) {
            return;
        }
        dfs(root.left);

        // 双向链表
        root.left = tail;
        tail.right = root;
        tail = root;

        dfs(root.right);
    }

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }
}